 /*
 * introsort.h
 *
 * Created 6/13/2009 By Johnny Huynh
 *
 * Version 00.00.02 6/28/2009
 *
 * Copyright Information:
 * All content copyright © 2009 Johnny Huynh. All rights reserved.
 *
 * The below code is modified from ralphunden.net (http://ralphunden.net/?q=a-guide-to-introsort#4).
 * Please give Ralph Unden due credit.
 */
 
 /*
  * In order to use introsort for a custom class, the copy constructor must be defined and the operator= must
  * be overloaded.
  */
 
 #ifndef INTROSORT_H
 #define INTROSORT_H
 
 template <typename TYPENAME> inline void introsort( TYPENAME* a, size_t size );
 template <typename TYPENAME> inline void introsort( TYPENAME* a, size_t begin, size_t end );
 template <typename TYPENAME> inline void introsort_loop ( TYPENAME* a, size_t begin, size_t end, size_t depth_limit );
 template <typename TYPENAME> inline size_t partition( TYPENAME* a, size_t begin, size_t end, TYPENAME pivot );
 template <typename TYPENAME> inline TYPENAME medianof3(TYPENAME* a, size_t begin, size_t mid, size_t end);
 template <typename TYPENAME> inline void heapsort(TYPENAME* a, size_t begin, size_t end);
 template <typename TYPENAME> inline void downheap(TYPENAME* a, size_t i, size_t n, size_t begin);
 template <typename TYPENAME> inline void insertionsort(TYPENAME* a, size_t begin, size_t end);
 template <typename TYPENAME> inline TYPENAME floor_lg(TYPENAME s);
 
 template <typename TYPENAME> inline void introsort( TYPENAME* a, size_t size, 
                                                    bool(*compare)(const TYPENAME&, const TYPENAME&) );
 template <typename TYPENAME> inline void introsort( TYPENAME* a, size_t begin, size_t end, 
                                                    bool(*compare)(const TYPENAME&, const TYPENAME&) );
 template <typename TYPENAME> inline void introsort_loop ( TYPENAME* a, size_t begin, size_t end, size_t depth_limit, 
                                                    bool(*compare)(const TYPENAME&, const TYPENAME&) );
 template <typename TYPENAME> inline size_t partition( TYPENAME* a, size_t begin, size_t end, TYPENAME pivot, 
                                                    bool(*compare)(const TYPENAME&, const TYPENAME&) );
 template <typename TYPENAME> inline TYPENAME medianof3(TYPENAME* a, size_t begin, size_t mid, size_t end, 
                                                    bool(*compare)(const TYPENAME&, const TYPENAME&));
 template <typename TYPENAME> inline void heapsort(TYPENAME* a, size_t begin, size_t end, 
                                                    bool(*compare)(const TYPENAME&, const TYPENAME&));
 template <typename TYPENAME> inline void downheap(TYPENAME* a, size_t i, size_t n, size_t begin, 
                                                    bool(*compare)(const TYPENAME&, const TYPENAME&));
 template <typename TYPENAME> inline void insertionsort(TYPENAME* a, size_t begin, size_t end, 
                                                    bool(*compare)(const TYPENAME&, const TYPENAME&));
 
 // Example declaration of array a of size 5:
 // short a[] { 5, 4, 3, 2, 1 }
 // Example declaration of a compareValuesList of size 2:
 // int b[] = { 1, 2, 3, 3, 5 };
 // int c[] = { 34, 1, 21, -12, 1 };
 // int* compareValuesList[] = { b, c };
 // Example declaration of a compare list of size 2:
 // bool (*compareList[2])(const int& a, const int& b) = { introsort_ns::lessThan<int>, introsort_ns::lessThan<int> };
 template <typename T1, typename T2> 
 inline void introsort( T1* a, size_t size, T2** compareValuesList, size_t compareValuesListSize, 
                                                    bool(**compare)(const T2&, const T2&) );
 template <typename T1, typename T2>
 inline void introsort( T1* a, size_t begin, size_t end, T2** compareValuesList, size_t compareValuesListSize, 
                                                    bool(**compare)(const T2&, const T2&) );
 template <typename T1, typename T2>
 inline void introsort_loop ( T1* a, size_t begin, size_t end, size_t depth_limit, 
                            T2** compareValuesList, size_t compareValuesListSize, bool(**compare)(const T2&, const T2&) );
 template <typename T1, typename T2> 
 inline size_t partition( T1* a, size_t begin, size_t end, T1 pivot, T2** compareValuesList, 
                                                    size_t compareValuesListSize, bool(**compare)(const T2&, const T2&) );
 template <typename T1, typename T2>
 inline size_t medianof3(T1* a, size_t begin, size_t mid, size_t end, T2** compareValuesList, 
                                                    size_t compareValuesListSize, bool(**compare)(const T2&, const T2&));
 template <typename T1, typename T2> 
 inline void heapsort(T1* a, size_t begin, size_t end, T2** compareValuesList, 
                                                    size_t compareValuesListSize, bool(**compare)(const T2&, const T2&));
 template <typename T1, typename T2>
 inline void downheap(T1* a, size_t i, size_t n, size_t begin, T2** compareValuesList, 
                                                    size_t compareValuesListSize, bool(**compare)(const T2&, const T2&));
 template <typename T1, typename T2>
 inline void insertionsort(T1* a, size_t begin, size_t end, T2** compareValuesList, 
                                                    size_t compareValuesListSize, bool(**compare)(const T2&, const T2&));
 
 #include <algorithm>
 #include <cassert>
 #include <ctime>
 #include <math.h>
 
 /*
  * introsort_ns namespace
  */
 namespace introsort_ns
 {
    static size_t size_threshold = 16;
    
    template < typename TYPENAME > inline void swap( TYPENAME& element1, TYPENAME& element2 );
    
    template < typename TYPENAME >
    inline void getListOfValues( std::vector< TYPENAME >& v, 
                                    const size_t& index, TYPENAME** compareValuesList, size_t compareValuesListSize );
    
    template < typename TYPENAME >
    inline void swap( const size_t& indexA, const size_t& indexB, TYPENAME** compareValuesList, 
                                                                  size_t compareValuesListSize );
    
    template < typename TYPENAME >
    inline void set_A_equal_B( const size_t& indexA, const size_t& indexB, TYPENAME** compareValuesList, 
                                                                    size_t compareValuesListSize );
    
    template < typename TYPENAME >
    inline void set_A_equal_Values( const size_t& indexA, TYPENAME* values, TYPENAME** compareValuesList, 
                                                                    size_t compareValuesListSize );
                                                                    
    template < typename TYPENAME > 
    inline bool compare( const size_t& indexA, const size_t& indexB, 
             TYPENAME** compareValuesList, size_t compareValuesListSize, bool(**compare)(const TYPENAME&, const TYPENAME&) );
    
    template < typename TYPENAME > 
    inline bool compare( const size_t& indexA, TYPENAME* values, 
             TYPENAME** compareValuesList, size_t compareValuesListSize, bool(**compare)(const TYPENAME&, const TYPENAME&) );
    
    template < typename TYPENAME > 
    inline bool compare( TYPENAME* values, const size_t& indexB, 
             TYPENAME** compareValuesList, size_t compareValuesListSize, bool(**compare)(const TYPENAME&, const TYPENAME&) );
    
    template< typename TYPENAME >
    inline bool lessThan( const TYPENAME& a, const TYPENAME& b ) { return a < b; }
    
    template< typename TYPENAME >
    inline bool greaterThan( const TYPENAME& a, const TYPENAME& b ) { return a > b; }
 }



 /**
  * introsort
  */
 template <typename TYPENAME>
 inline void introsort( TYPENAME* a, size_t size )
 {
    introsort_loop(a, 0, size, floor_lg(size) << 0x1); //2*floor_lg(size));
    insertionsort(a, 0, size);
 }
 
 /**
  * introsort
  */
 template <typename TYPENAME>
 inline void introsort( TYPENAME* a, size_t size, bool(*compare)(const TYPENAME&, const TYPENAME&) )
 {
    introsort_loop(a, 0, size, floor_lg(size) << 0x1, compare);
    insertionsort(a, 0, size, compare);
 }
 
 /**
  * introsort
  */
 template <typename T1, typename T2>
 inline void introsort( T1* a, size_t size, T2** compareValuesList, size_t compareValuesListSize, 
                                                    bool(**compare)(const T2&, const T2&) )
 {
    introsort_loop(a, 0, size, floor_lg(size) << 0x1, compareValuesList, compareValuesListSize, compare);
    insertionsort(a, 0, size, compareValuesList, compareValuesListSize, compare);
 }
 
 template <typename TYPENAME>
 inline void introsort( TYPENAME* a, size_t begin, size_t end )
 {
    if (begin < end)
    {
	    introsort_loop(a, begin, end, floor_lg(end-begin) << 0x1); //2*floor_lg(end-begin));
	    insertionsort(a, begin, end);
    }
 }
 
 template <typename TYPENAME>
 inline void introsort( TYPENAME* a, size_t begin, size_t end, bool(*compare)(const TYPENAME&, const TYPENAME&) )
 {
    if (begin < end)
    {
	    introsort_loop(a, begin, end, floor_lg(end-begin) << 0x1, compare);
	    insertionsort(a, begin, end, compare);
    }
 }
 
 template <typename T1, typename T2>
 inline void introsort( T1* a, size_t begin, size_t end, T2** compareValuesList, 
                                                        size_t compareValuesListSize, bool(**compare)(const T2&, const T2&) )
 {
    if (begin < end)
    {
	    introsort_loop(a, begin, end, floor_lg(end-begin) << 0x1, compareValuesList, compareValuesListSize, compare);
	    insertionsort(a, begin, end, compareValuesList, compareValuesListSize, compare);
    }
 }

 /*
  * Quicksort algorithm modified for Introsort
  */
 template <typename TYPENAME>
 inline void introsort_loop ( TYPENAME* a, size_t begin, size_t end, size_t depth_limit )
 {
    while (end - begin > introsort_ns::size_threshold)
    {
        if (depth_limit == 0)
        {
    	    heapsort(a, begin, end);
    		return;
    	}
    	depth_limit = depth_limit - 1;
    	size_t p( partition(a, begin, end, medianof3(a, begin, begin + ((end-begin) >> 0x1)+1, end-1)) );
	    //size_t p = partition(a, begin, end, medianof3(a, begin, begin + ((end-begin)/2)+1, end-1));
	    introsort_loop(a, p, end, depth_limit);
	    end = p;
    }
 }
 
 /*
  * Quicksort algorithm modified for Introsort
  */
 template <typename TYPENAME>
 inline void introsort_loop ( TYPENAME* a, size_t begin, size_t end, size_t depth_limit, 
                                                         bool(*compare)(const TYPENAME&, const TYPENAME&) )
 {
    while (end - begin > introsort_ns::size_threshold)
    {
        if (depth_limit == 0)
        {
    	    heapsort(a, begin, end, compare);
    		return;
    	}
    	depth_limit = depth_limit - 1;
    	size_t p( partition(a, begin, end, medianof3(a, begin, begin + ((end-begin) >> 0x1)+1, end-1, compare), compare) );
	    introsort_loop(a, p, end, depth_limit, compare);
	    end = p;
    }
 }
 
 /*
  * Quicksort algorithm modified for Introsort
  */
 template <typename T1, typename T2>
 inline void introsort_loop ( T1* a, size_t begin, size_t end, size_t depth_limit, T2** compareValuesList, 
                                                        size_t compareValuesListSize, bool(**compare)(const T2&, const T2&) )
 {
    while (end - begin > introsort_ns::size_threshold)
    {
        if (depth_limit == 0)
        {
    	    heapsort(a, begin, end, compareValuesList, compareValuesListSize, compare);
    		return;
    	}
    	depth_limit = depth_limit - 1;
    	size_t p( partition(a, begin, end, 
    	    medianof3(a, begin, begin + ((end-begin) >> 0x1)+1, end-1, compareValuesList, compareValuesListSize, compare), 
    	                                                            compareValuesList, compareValuesListSize, compare) );
	    introsort_loop(a, p, end, depth_limit, compareValuesList, compareValuesListSize, compare);
	    end = p;
    }
 }

 template <typename TYPENAME>
 inline size_t partition( TYPENAME* a, size_t begin, size_t end, TYPENAME pivot )
 {
    size_t i(begin), j(end);
    while (true)
    {
        while (a[i] < pivot) ++i; // compare
        //--j;
        //while (pivot < a[j]) --j; // compare
        while (pivot < a[--j]); // compare
        //if(!(i < j))
        if ( i >= j )
    	    return i;
        introsort_ns::swap(a[i], a[j]);
        ++i;
    }
 }
 
 template <typename TYPENAME>
 inline size_t partition( TYPENAME* a, size_t begin, size_t end, TYPENAME pivot, bool(*compare)(const TYPENAME&, const TYPENAME&) )
 {
    size_t i(begin), j(end);
    while (true)
    {
        while ( compare( a[i], pivot ) ) ++i; // compare
        
        while ( compare( pivot, a[--j] ) ); // compare
        
        if ( i >= j )
    	    return i;

        introsort_ns::swap(a[i], a[j]);
        ++i;
    }
 }

 template <typename T1, typename T2>
 inline size_t partition( T1* a, size_t begin, size_t end, size_t pivot, T2** compareValuesList, 
                                                        size_t compareValuesListSize, bool(**compare)(const T2&, const T2&) )
 {
    size_t i(begin), j(end);
    while (true)
    {
        while ( introsort_ns::compare( i, pivot, compareValuesList, compareValuesListSize, compare ) ) ++i; // compare
        
        while ( introsort_ns::compare( pivot, --j, compareValuesList, compareValuesListSize, compare ) ); // compare
        
        if ( i >= j )
    	    return i;

        introsort_ns::swap( a[i], a[j] );
        introsort_ns::swap( i, j, compareValuesList, compareValuesListSize );
        ++i;
    }
 }
 
 template <typename TYPENAME>
 inline TYPENAME medianof3(TYPENAME* a, size_t begin, size_t mid, size_t end)
 {
    if (a[mid] < a[begin])  // compare
    {
        if (a[end] < a[mid]) // compare
            return a[mid];
        else
        {
            if (a[end] < a[begin]) // compare
		        return a[end];
		    else
		        return a[begin];
        }
    }
	else
	{
        if (a[end] < a[mid]) // compare
        {
            if (a[end] < a[begin]) // compare
		        return a[begin];
		    else
		        return a[end];
        }
        else
            return a[mid];
	}
 }
 
 template <typename TYPENAME>
 inline TYPENAME medianof3(TYPENAME* a, size_t begin, size_t mid, size_t end, bool(*compare)(const TYPENAME&, const TYPENAME&) )
 {
    if ( compare( a[mid], a[begin] ) )  // compare
    {
        if ( compare( a[end], a[mid] ) ) // compare
            return a[mid];
        else
        {
            if ( compare( a[end], a[begin] ) ) // compare
		        return a[end];
		    else
		        return a[begin];
        }
    }
	else
	{
        if ( compare( a[end], a[mid] ) ) // compare
        {
            if ( compare( a[end], a[begin] ) ) // compare
		        return a[begin];
		    else
		        return a[end];
        }
        else
            return a[mid];
	}
 }
 
 template <typename T1, typename T2>
 inline size_t medianof3(T1* a, size_t begin, size_t mid, size_t end, T2** compareValuesList, 
                                                        size_t compareValuesListSize, bool(**compare)(const T2&, const T2&) )
 {
    if ( introsort_ns::compare( mid, begin, compareValuesList, compareValuesListSize, compare ) )  // compare
    {
        if ( introsort_ns::compare( end, mid, compareValuesList, compareValuesListSize, compare ) ) // compare
            return mid;
        else
        {
            if ( introsort_ns::compare( end, begin, compareValuesList, compareValuesListSize, compare ) ) // compare
		        return end;
		    else
		        return begin;
        }
    }
	else
	{
        if ( introsort_ns::compare( end, mid, compareValuesList, compareValuesListSize, compare ) ) // compare
        {
            if ( introsort_ns::compare( end, begin, compareValuesList, compareValuesListSize, compare ) ) // compare
		        return begin;
		    else
		        return end;
        }
        else
            return mid;
	}
 }
 
 /**
  * Heapsort algorithm
  */
 template <typename TYPENAME>
 inline void heapsort(TYPENAME* a, size_t begin, size_t end)
 {
    size_t n(end-begin);
    for (size_t i(n >> 0x1); i >= 1; --i) // (n >> 0x1) == n/2
    {
        downheap(a, i, n, begin);
    }
    /*for (size_t i = n; i > 1; --i)
    {
	    swap(a[begin], a[begin+i-1]);
        downheap(a, 1, i-1, begin);
    }*/
    for (size_t i(n); i > 1; )
    {
	    introsort_ns::swap(a[begin], a[begin+(--i)]);
        downheap(a, 1, i, begin);
    }
 }
 
 /**
  * Heapsort algorithm
  */
 template <typename TYPENAME>
 inline void heapsort(TYPENAME* a, size_t begin, size_t end, bool(*compare)(const TYPENAME&, const TYPENAME&) )
 {
    size_t n(end-begin);
    for (size_t i(n >> 0x1); i >= 1; --i)
    {
        downheap(a, i, n, begin, compare);
    }

    for (size_t i(n); i > 1; )
    {
	    introsort_ns::swap(a[begin], a[begin+(--i)]);
        downheap(a, 1, i, begin, compare);
    }
 }

 /**
  * Heapsort algorithm
  */
 template <typename T1, typename T2>
 inline void heapsort(T1* a, size_t begin, size_t end, T2** compareValuesList, 
                                                        size_t compareValuesListSize, bool(**compare)(const T2&, const T2&) )
 {
    size_t n(end-begin);
    for (size_t i(n >> 0x1); i >= 1; --i)
    {
        downheap(a, i, n, begin, compareValuesList, compareValuesListSize, compare );
    }

    for (size_t i(n); i > 1; )
    {
	    introsort_ns::swap(a[begin], a[begin+(--i)]);
	    introsort_ns::swap( begin, begin+i, compareValuesList, compareValuesListSize );
        downheap( a, 1, i, begin, compareValuesList, compareValuesListSize, compare );
    }
 }

 template <typename TYPENAME>
 inline void downheap(TYPENAME* a, size_t i, size_t n, size_t begin)
 {
    /*TYPENAME d = a[begin+i-1];
    size_t child;
    while (i <= (n >> 0x1)) // (n >> 0x1) == n/2
	{
	   child = 2*i;
	   if (child < n && a[begin+child-1] < a[begin+child]) // compare
	   {
	       ++child;
	   }
	   if (!(d < a[begin+child-1])) break; // compare
	   a[begin+i-1] = a[begin+child-1];
	   i = child;
	}
	a[begin+i-1] = d;*/
	TYPENAME d( a[begin+(--i)] );
    size_t child;
    while (i <= (n >> 0x1)) // (n >> 0x1) == n/2
	{
	   child = (i+1) << 0x1;//2*(i+1);
	   if (child < n && a[begin+child-1] < a[begin+child]) // compare
	   {
	       ++child;
	   }
	   if (!(d < a[begin+child-1])) break; // compare
	   a[begin+i] = a[begin+child-1];
	   i = child;
	}
	a[begin+i] = d;
 }

 template <typename TYPENAME>
 inline void downheap(TYPENAME* a, size_t i, size_t n, size_t begin, bool(*compare)(const TYPENAME&, const TYPENAME&) )
 {
	TYPENAME d( a[begin+(--i)] );
    size_t child;
    while (i <= (n >> 0x1)) // (n >> 0x1) == n/2
	{
	   child = (i+1) << 0x1;
	   if ( child < n && compare( a[begin+child-1], a[begin+child] ) ) // compare
	   {
	       ++child;
	   }
	   if ( compare( a[begin+child-1], d ) ) break; // compare
	   a[begin+i] = a[begin+child-1];
	   i = child;
	}
	a[begin+i] = d;
 }
 
 template <typename T1, typename T2>
 inline void downheap(T1* a, size_t i, size_t n, size_t begin, T2** compareValuesList, 
                                                        size_t compareValuesListSize, bool(**compare)(const T2&, const T2&) )
 {
    /*size_t di = begin+(--i);
	//TYPENAME d = a[di];
    size_t child;
    while (i <= (n >> 0x1)) // (n >> 0x1) == n/2
	{
	   child = 2*(i+1);
	   if ( child < n 
	    && introsort_ns::compare( begin+child-1, begin+child, compareValuesList, compareValuesListSize, compare ) ) // compare
	   {
	       ++child;
	   }
	   if ( introsort_ns::compare( begin+child-1, di, compareValuesList, compareValuesListSize, compare ) ) break; // compare
	   a[begin+i] = a[begin+child-1];
	   introsort_ns::set_A_equal_B( begin+i, begin+child-1, compareValuesList, compareValuesListSize );
	   i = child;
	}
	a[begin+i] = a[di];
	introsort_ns::set_A_equal_B( begin+i, di, compareValuesList, compareValuesListSize );*/
	
	T1 d( a[begin+(--i)] );
	std::vector<T2> d2( compareValuesListSize );
	introsort_ns::getListOfValues( d2, begin+i, compareValuesList, compareValuesListSize );
    size_t child;
    while (i <= (n >> 0x1)) // (n >> 0x1) == n/2
	{
	   child = (i+1) << 0x1;
	   if ( child < n 
	    && introsort_ns::compare( begin+child-1, begin+child, compareValuesList, compareValuesListSize, compare ) ) // compare
	   {
	       ++child;
	   }
	   if ( introsort_ns::compare( begin+child-1, &(d2[0]), compareValuesList, compareValuesListSize, compare ) )
	        break; // compare
	   
	   a[begin+i] = a[begin+child-1];
	   introsort_ns::set_A_equal_B( begin+i, begin+child-1, compareValuesList, compareValuesListSize );
	   i = child;
	}
	a[begin+i] = d;
	introsort_ns::set_A_equal_Values( begin+i, &d2[0], compareValuesList, compareValuesListSize );
 }

 /**
  * Insertion sort algorithm
  */
 template <typename TYPENAME>
 inline void insertionsort(TYPENAME* a, size_t begin, size_t end)
 {
    size_t i,j;
	TYPENAME t;
	for (i = begin; i < end; ++i)
	{
        j = i;
	    t = a[i];
	    while(j != begin && t < a[j-1]) // compare
	    {
	        a[j] = a[j-1];
		    --j;
	    }
	    a[j] = t;
    }
    /*size_t i,j;
	TYPENAME t;
	for (i = begin; i < end; ++i)
	{
        j = i;
	    t = a[i];
	    while(t < a[--j] && j != begin) // compare
	    {
	        a[j+1] = a[j];
	    }
	    a[++j] = t;
    }*/
 }
 
 /**
  * Insertion sort algorithm
  */
 template <typename TYPENAME>
 inline void insertionsort(TYPENAME* a, size_t begin, size_t end, bool(*compare)(const TYPENAME&, const TYPENAME&) )
 {
    size_t i,j;
	TYPENAME t;
	for (i = begin; i < end; ++i)
	{
        j = i;
	    t = a[i];
	    while(j != begin && compare(t, a[j-1])) // compare
	    {
	        a[j] = a[j-1];
		    --j;
	    }
	    a[j] = t;
    }
    /*
    size_t i,j;
	TYPENAME t;
	for (i = begin; i < end; ++i)
	{
        j = i;
	    t = a[i];
	    while( compare( t, a[--j] ) && j != begin) // compare
	    {
	        a[j+1] = a[j];
	    }
	    a[++j] = t;
    }*/
 }
 
 /**
  * Insertion sort algorithm
  */
 template <typename T1, typename T2>
 inline void insertionsort(T1* a, size_t begin, size_t end, T2** compareValuesList, 
                                                        size_t compareValuesListSize, bool(**compare)(const T2&, const T2&) )
 {
    size_t i,j;
	T1 t;
	std::vector<T2> t2( compareValuesListSize );
	for (i = begin; i < end; ++i)
	{
        j = i;
	    t = a[i];
	    introsort_ns::getListOfValues( t2, i, compareValuesList, compareValuesListSize );
	    while(j != begin && introsort_ns::compare( &t2[0], j-1, compareValuesList, compareValuesListSize, compare ) ) // compare
	    {
	        a[j] = a[j-1];
	        introsort_ns::set_A_equal_B( j, j-1, compareValuesList, compareValuesListSize );
		    --j;
	    }
	    a[j] = t;
	    introsort_ns::set_A_equal_Values( j, &t2[0], compareValuesList, compareValuesListSize );
    }
    /*
    size_t i,j;
	T1 t;
	std::vector<T2> t2( compareValuesListSize );
	for (i = begin; i < end; ++i)
	{
        j = i;
	    t = a[i];
	    t2 = introsort_ns::getListOfValues( i, compareValuesList, compareValuesListSize );
	    while( introsort_ns::compare( &t2[0], --j, compareValuesList, compareValuesListSize, compare ) 
	            && j != begin) // compare
	    {
	        a[j+1] = a[j];
	        introsort_ns::set_A_equal_B( j+1, j, compareValuesList, compareValuesListSize );
	    }
	    a[++j] = t;
	    introsort_ns::set_A_equal_Values( j, &t2[0], compareValuesList, compareValuesListSize );
    }
    */
 }
 
 /**
  * floor_lg() returns the floor of the log of the specified value, s,
  * divided by log of 2.
  *
  * @param (TYPENAME) s
  * @return TYPENAME
  */
 template <typename TYPENAME>
 inline TYPENAME floor_lg(TYPENAME s)
 {
    return (TYPENAME)floor(log((double)s)/log(2.0));
 }
    
 /**
  * swap() switches the specified first element with the specified second element
  *
  * @param (TYPENAME&)element1, (TYPENAME&)element2
  */
 template < typename TYPENAME >
 inline void introsort_ns::swap( TYPENAME& element1, TYPENAME& element2 )
 {
    TYPENAME temp( element1 );
    element1 = element2;
    element2 = temp;
 }
 
 /**
  * getListOfValues() returns the values of the comparison list at the specified index.
  *
  * @param (const size_t&) index
  * @param (TYPENAME**) compareValuesList
  * @param (size_t) compareValuesListSize
  */
 template < typename TYPENAME >
 inline void introsort_ns::getListOfValues( std::vector< TYPENAME >& v, const size_t& index, 
                                            TYPENAME** compareValuesList, size_t compareValuesListSize )
 {
    v.clear();
    for ( size_t i( 0x0 ); i < compareValuesListSize; ++i )
    {
        v.push_back( compareValuesList[i][index] );
    }
 }
    
 /**
  * swap() swaps the values of all the comparison list for the two specified indexes.
  *
  * @param (const size_t&) indexA
  * @param (const size_t&) indexB
  * @param (TYPENAME**) compareValuesList
  * @param (size_t) compareValuesListSize
  */
 template < typename TYPENAME >
 inline void introsort_ns::swap( const size_t& indexA, const size_t& indexB, TYPENAME** compareValuesList, 
                                                                      size_t compareValuesListSize )
 {
    for ( size_t i( 0x0 ); i < compareValuesListSize; ++i )
    {
        introsort_ns::swap( compareValuesList[i][indexA], compareValuesList[i][indexB] );
    }
 }
 
 /**
  * set_A_equal_B() sets the values of all the comparison list for the indexA to the values at indexB.
  *
  * @param (const size_t&) indexA
  * @param (const size_t&) indexB
  * @param (TYPENAME**) compareValuesList
  * @param (size_t) compareValuesListSize
  */
 template < typename TYPENAME >
 inline void introsort_ns::set_A_equal_B( const size_t& indexA, const size_t& indexB, TYPENAME** compareValuesList, 
                                                                    size_t compareValuesListSize )
 {
    for ( size_t i( 0x0 ); i < compareValuesListSize; ++i )
    {
        compareValuesList[i][indexA] = compareValuesList[i][indexB];
    }
 }
 
 /**
  * set_A_equal_Values() sets the values of all the comparison list for the indexA to the values in values list.
  *
  * @param (const size_t&) indexA
  * @param (TYPENAME*) values
  * @param (TYPENAME**) compareValuesList
  * @param (size_t) compareValuesListSize
  */
 template < typename TYPENAME >
 inline void introsort_ns::set_A_equal_Values( const size_t& indexA, TYPENAME* values, TYPENAME** compareValuesList, 
                                                                    size_t compareValuesListSize )
 {
    for ( size_t i( 0x0 ); i < compareValuesListSize; ++i )
    {
        compareValuesList[i][indexA] = values[i];
    }
 }
 
 /**
  * compare() compares the values of all the comparison list for the two specified indexes using the associated 
  * compare functions.
  *
  * @param (const size_t&) indexA
  * @param (const size_t&) indexB
  * @param (TYPENAME**) compareValuesList
  * @param (size_t) compareValuesListSize
  * @param (bool(**function)(const TYPENAME&, const TYPENAME&)) compare
  * @return bool
  */
 template < typename TYPENAME > 
 inline bool introsort_ns::compare( const size_t& indexA, const size_t& indexB, 
               TYPENAME** compareValuesList, size_t compareValuesListSize, bool(**compare)(const TYPENAME&, const TYPENAME&) )
 {
    for ( size_t i( 0x0 ); i < compareValuesListSize; ++i )
    {
        if ( compare[i](compareValuesList[i][indexA], compareValuesList[i][indexB]) )
            return true;
        else if ( compareValuesList[i][indexA] == compareValuesList[i][indexB] )
        {
        
        }
        else
            return false;
    }
    
    return false;
 }
 
 /**
  * compare() compares the values of all the comparison list for the specified index with the specified values using the 
  * associated compare functions.
  *
  * @param (const size_t&) indexA
  * @param (TYPENAME*) values
  * @param (TYPENAME**) compareValuesList
  * @param (size_t) compareValuesListSize
  * @param (bool(**function)(const TYPENAME&, const TYPENAME&)) compare
  * @return bool
  */
 template < typename TYPENAME > 
 inline bool introsort_ns::compare( const size_t& indexA, TYPENAME* values, 
             TYPENAME** compareValuesList, size_t compareValuesListSize, bool(**compare)(const TYPENAME&, const TYPENAME&) )
 {
    for ( size_t i( 0x0 ); i < compareValuesListSize; ++i )
    {
        if ( compare[i](compareValuesList[i][indexA], values[i]) )
            return true;
        else if ( compareValuesList[i][indexA] == values[i] )
        {
        
        }
        else
            return false;
    }
    
    return false;
 }
 
 /**
  * compare() compares the specified values with the values of all the comparison list for the specified index using the 
  * associated compare functions.
  *
  * @param (TYPENAME*) values
  * @param (const size_t&) indexB
  * @param (TYPENAME**) compareValuesList
  * @param (size_t) compareValuesListSize
  * @param (bool(**function)(const TYPENAME&, const TYPENAME&)) compare
  * @return bool
  */
 template < typename TYPENAME > 
 inline bool introsort_ns::compare( TYPENAME* values, const size_t& indexB, 
             TYPENAME** compareValuesList, size_t compareValuesListSize, bool(**compare)(const TYPENAME&, const TYPENAME&) )
 {
    for ( size_t i( 0x0 ); i < compareValuesListSize; ++i )
    {
        if ( compare[i](values[i], compareValuesList[i][indexB]) )
            return true;
        else if (  values[i] == compareValuesList[i][indexB] )
        {
        
        }
        else
            return false;
    }
    
    return false;
 }
 
 #endif // INTROSORT_H